﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& price, int target) {
    int left = 0, right = price.size() - 1;
    while (left < right) {
        int sum = price[left] + price[right];
        if (sum == target) {
            return { price[left], price[right] };
        }
        else if (sum < target) {
            ++left;
        }
        else {
            --right;
        }
    }
    return {};
}

vector<vector<int>> threeSum(vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    int n = nums.size();
    for (int i = 0; i < nums.size();)
    {
        int left = 0;
        int right = n - 1;
        int target = -nums[i];
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum < target)
            {
                left++;
            }
            else if (sum>target)
            {
                right--;
            }
            else
            {
                ret.push_back({ nums[i], nums[left], nums[right] });
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
            }
        }
        i++;
        while (i < n && nums[i] == nums[i - 1])i++;
    }
    return ret;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> ret;
    // 1. 排序
    sort(nums.begin(), nums.end());
    // 2. 利⽤双指针解决问题
    int n = nums.size();
    for (int i = 0; i < n;) // 固定数 a
    {
        // 利⽤ 三数之和
        for (int j = i + 1; j < n;) // 固定数 b
        {
            // 双指针
            int left = j + 1, right = n - 1;
            long long aim = (long long)target - nums[i] - nums[j];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum < aim)
                    left++;
                else if (sum > aim)
                    right--;
                else {
                    ret.push_back(
                        { nums[i], nums[j], nums[left++], nums[right--] });
                    // 去重⼀
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            // 去重⼆
            j++;
            while (j < n && nums[j] == nums[j - 1])
                j++;
        }
        // 去重三
        i++;
        while (i < n && nums[i] == nums[i - 1])
            i++;
    }
    return ret;
}

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    int min_len = INT_MAX;  // 记录最短子数组长度，初始设为最大值
    int window_sum = 0;     // 滑动窗口内元素的和

    // 使用滑动窗口 [left, right]
    for (int left = 0, right = 0; right < n; right++) {
        window_sum += nums[right];  // 将当前元素加入窗口

        // 当窗口和 >= 目标值时，尝试缩小子数组长度
        while (window_sum >= target) {
            min_len = std::min(min_len, right - left + 1);  // 更新最小长度
            window_sum -= nums[left];   // 缩小窗口：左指针右移
            left++;                     // 左指针移动后更新窗口和
        }
    }

    return min_len == INT_MAX ? 0 : min_len;  // 若没有解返回0
}
int numJewelsInStones(string jewels, string stones) {
    unordered_map<char, int> pCount;
    for (char c : jewels) {
        pCount[c]++;
    }
    int count = 0;
    for (char ch : stones)
    {
        if (pCount[ch] > 0)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    vector<int> nums1 = { 3, 9, 12, 15 };
    vector<vector<int>>arr = threeSum(nums1);
    return 0;
}